package nl.xs4all.dylanschell.deckprinter.util

/**
 * Created by IntelliJ IDEA.
 * User: dylan
 * Date: 21-12-10
 * Time: 21:21
 * To change this template use File | Settings | File Templates.
 */

object SDistance
{
  //*****************************
  // Compute Levenshtein distance
  //*****************************
  def distance(s: String, t: String): Int = {
    var n = s.length
    var m = t.length
    if (n == 0) return m
    if (m == 0) return n
    val d: Array[Array[Int]] = Array.ofDim(n + 1, m + 2);
    var cost = 0

    for (i <- 0 until d.length) d(i)(0) = i;

    for (i <- 1 to n) {
      var s_i = s.charAt(i - 1)
      for (j <- 1 to m) {
        var t_j = t.charAt(j - 1)
        if (s_i == t_j) {
          cost = 0
        }
        else {
          cost = 1
        }
        d(i)(j) = minimum(d(i - 1)(j) + 1, d(i)(j - 1) + 1, d(i - 1)(j - 1) + cost)
      }
    }
    return d(n)(m);
  }

  private def minimum(a: Int, b: Int, c: Int): Int = Set(a, b, c).min
}